Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations

摘要

We present algorithms for the type-IV discrete cosine transform (DCT-IV) anddiscrete sine transform (DST-IV), as well as for the modified discrete cosinetransform (MDCT) and its inverse, that achieve a lower count of realmultiplications and additions than previously published algorithms, withoutsacrificing numerical accuracy. Asymptotically, the operation count is reducedfrom ~2NlogN to ~(17/9)NlogN for a power-of-two transform size N, and the exactcount is strictly lowered for all N > 4. These results are derived byconsidering the DCT to be a special case of a DFT of length 8N, with certainsymmetries, and then pruning redundant operations from a recent improved fastFourier transform algorithm (based on a recursive rescaling of theconjugate-pair split radix algorithm). The improved algorithms for DST-IV andMDCT follow immediately from the improved count for the DCT-IV.